package algorithm.leetcode.medium;

/*
 给定一个非负整数 n，计算各位数字都不同的数字 x 的个数，其中 0 ≤ x < 10n 。
 */

/**
 * @author jack.wu
 * @version 1.0
 * @date 2021/1/13
 */
public class Question357 {

    public static void main(String[] args) {
        Question357 question = new Question357();
        int digits = question.countNumbersWithUniqueDigits(2);
        System.out.println(digits);
    }

    /**
     * 思路： 排列组合
     * 先当n == 0返回1，n > 10相当于n = 10的结果
     * 对于n的答案，结果应该是n - 1的答案加上n位数的答案
     * n位数的答案怎么求得呢？最高位选择方案数为9种（0不能打头），
     * 第2位有9种方案（除了第一位剩余的9个数字都可以选）、第3位有8种...
     */
    public int countNumbersWithUniqueDigits(int n) {
        if (n == 0) {
            return 1;
        }
        n = Math.min(n, 10);
        int res = 10;
        int base = 9;
        int sum = 9;
        for (int i = 1; i < n; i++) {
            sum *= base--;
            res += sum;
        }
        return res;
    }


}
